#ifndef __SORT_H
#define __SORT_H
#include "utils.h"

template<typename T>
int partion(T* arr, int low, int high)
{
    int i = low;
    int j = high;

    T pivot = arr[low];

    while (i < j)
	{
		while (i<j && arr[j]>pivot) //从右向左开始找一个 小于等于 pivot的数值
		{
			j--;
		}
		if (i < j)
		{
			swap(&arr[i++], &arr[j]);  //r[i]和r[j]交换后 i 向右移动一位
		}
		while (i < j && arr[i] <= pivot) //从左向右开始找一个 大于 pivot的数值
		{
			i++;
		}
		if (i < j)
		{
			swap(&arr[i], &arr[j--]);  //r[i]和r[j]交换后 i 向左移动一位
		}
	}
	return i;  //返回最终划分完成后基准元素所在的位置

}

template<typename T>
void quick_sort(T arr[], int low, int high)
{
    if (low >= high)
        return;
    int mid = partion(arr, low, high);
    quick_sort(arr, low, mid - 1);
    quick_sort(arr, mid + 1, high);
}
#endif
